L3GO (Layout using Gridded Glyph Geometry Objects) is an ongoing project for improving the manufacturability of VLSI designs. L3GO provides a restricted set of objects that describes circuit connectivity and devices, referred to as glyphs. L3GO has three types of glyphs, including:
1. Stick glyphs, which are 1-dimensional line segments drawn between two grid points, e.g., used to describe FET gates or for interconnections. The attached properties of a stick glyph include which layer the stick belongs to, the start and end point, and a target width;
2. Contact glyphs, which are 0-dimensional points lying at grid points, e.g., used to describe vertical interconnections (contacts and vias). The attached properties of a contact glyph include which layer the contact belongs to, and parameters that specify how contacts are to be arranged in a matrix, e.g., the number of rows and columns in the matrix, the size of each contact, the horizontal and vertical distances between columns and rows, respectively and an optional offset of the matrix center relative to the glyph position; and
3. Area glyphs, which are 2-dimensional, axis aligned rectangles whose vertices are on grid points, e.g., used to describe diffusion regions.
In addition to their specific attributes, glyphs can carry ‘design intent’ attributes, e.g., net names, ratings of their importance, etc. A process called elaboration turns sets of glyphs into geometry (pre-data-prep mask shapes). A pattern describes a glyph configuration, e.g., a contact glyph with certain properties sitting on a stick glyph with another set of properties. Elaboration creates shapes for this configuration based on a set of parameters, e.g., it may create a pad on an M1 stick and four redundant vias on the pad.
The identification of predefined patterns is a key component of the elaboration process, as it significantly improves computational requirements. The possible configurations in a L3GO design are restricted compared to a shape based VLSI design. This suggests that redundant computations can be avoided through the identification of multiple placements of patterns in the design.
However, the direct description of L3GO features (points, sticks, boundary edges, etc.) as geometric objects does not lend itself to efficient recognition of patterns. Accordingly, a need exists for an efficient system for performing pattern recognition of L3GO features.